
import java.util.HashMap;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2022-12-31
 * Time: 23:23
 */

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution {
    public int pathSum(TreeNode root, int targetSum) {
        // 记录值为 Long 的前缀和的个数 Integer
        Map<Long, Integer> prefix=new HashMap<>(); // prefix 前缀和
        // 为了考虑某个节点的前缀和正好是 targetSum,如[1,1] 2 ,不加上的话,结果为0
        // 同时也考虑了某个节点的值就是 targetSum
        prefix.put(0L,1);
        return preOrder(root, 0L, prefix,targetSum);
    }

    public int preOrder(TreeNode root,Long sum,Map<Long,Integer> prefix,int targetSum){
        if(root==null){
            // 节点为空, 根本就达不到
            return 0;
        }
        int ret=0; // 记录这个节点及其之后的 满足要求的节点数目
        // if(root.val==targetSum){
        //     // 这个节点的值本身就等于 targetSum
        //     ret++;
        // }

        Long curValue=sum + root.val; // 记录这个节点的前缀和
        // 记录以这个节点为最后一个节点的满足条件的路径的数目
        ret+=prefix.getOrDefault(curValue-targetSum,0);
        // 更新前缀和
        prefix.put(curValue,prefix.getOrDefault(curValue,0)+1);
        // 加上它的后代满足条件的个数
        ret+=preOrder(root.left,curValue,prefix,targetSum);
        ret+=preOrder(root.right,curValue,prefix,targetSum);
        // 因为当前节点的前缀和 只对它的子孙有效 对其他节点无效 所以要从 map 中删除
        // 而他的后代节点已经遍历完了
        prefix.put(curValue,prefix.getOrDefault(curValue,0)-1);
        return ret;
    }
}
